{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Rectangle LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxRectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，其中每一行组成一个单词(自左向右)，每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。</p>\n",
    "\n",
    "<p>如果有多个面积最大的矩形，输出任意一个均可。一个单词可以重复使用。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>[&quot;this&quot;, &quot;real&quot;, &quot;hard&quot;, &quot;trh&quot;, &quot;hea&quot;, &quot;iar&quot;, &quot;sld&quot;]</code>\n",
    "<strong>输出:\n",
    "</strong><code>[\n",
    "&nbsp;  &quot;this&quot;,\n",
    "&nbsp;  &quot;real&quot;,\n",
    "&nbsp;  &quot;hard&quot;</code>\n",
    "]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>[&quot;aa&quot;]</code>\n",
    "<strong>输出: </strong>[&quot;aa&quot;,&quot;aa&quot;]</pre>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>words.length &lt;= 1000</code></li>\n",
    "\t<li><code>words[i].length &lt;= 100</code></li>\n",
    "\t<li>数据保证单词足够随机</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-rectangle-lcci](https://leetcode.cn/problems/word-rectangle-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-rectangle-lcci](https://leetcode.cn/problems/word-rectangle-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.words = []\n",
    "\n",
    "        self.word_map = dict()\n",
    "        self.word_all = dict()\n",
    "        self.word_len_max = 2  # 记录最大单词长度，便于后续遍历\n",
    "\n",
    "        self.ans_rect = None\n",
    "        self.ans_area = 0  # 记录当前算出的最大面积\n",
    "\n",
    "    def maxRectangle(self, words: [str]) -> [str]:\n",
    "        self.words = words\n",
    "        self.add_word_to_map()\n",
    "        self.check_up_edge()\n",
    "\n",
    "        return self.ans_rect\n",
    "\n",
    "    # 数据初始化\n",
    "    def add_word_to_map(self):\n",
    "        for word_pos, word in enumerate(self.words):\n",
    "            word_length = len(self.words[word_pos])\n",
    "            word_head = self.words[word_pos][:1]\n",
    "            word_end = self.words[word_pos][-1:]\n",
    "\n",
    "            if word_length not in self.word_map.keys():\n",
    "                self.word_map[word_length] = dict()\n",
    "            if word_head not in self.word_map[word_length].keys():\n",
    "                self.word_map[word_length][word_head] = dict()\n",
    "            if word_end not in self.word_map[word_length][word_head].keys():\n",
    "                self.word_map[word_length][word_head][word_end] = []\n",
    "            self.word_map[word_length][word_head][word_end].append(word_pos)\n",
    "\n",
    "            self.word_all[word] = word_pos\n",
    "            if word_length > self.word_len_max:\n",
    "                self.word_len_max = word_length\n",
    "\n",
    "    # 选取上边并准备进行检查\n",
    "    def check_up_edge(self):\n",
    "        for up_edge_len in range(self.word_len_max, 1, -1):\n",
    "            # 剪枝，如果上边长乘以最长边都得不到更大的面积，那就没必要算下去了\n",
    "            if up_edge_len * self.word_len_max <= self.ans_area:\n",
    "                break\n",
    "            if up_edge_len in self.word_map:\n",
    "                for up_edge_head in self.word_map[up_edge_len]:\n",
    "                    for up_edge_end in self.word_map[up_edge_len][up_edge_head]:\n",
    "                        for up_edge_word_pos in self.word_map[up_edge_len][up_edge_head][up_edge_end]:\n",
    "                            # up_edge_word_pos 为上边候选，接下来选取左边候选\n",
    "                            self.check_left_edge(self.words[up_edge_word_pos])\n",
    "\n",
    "    # 根据上边，选取左边并准备进行检查\n",
    "    def check_left_edge(self, up_edge_word):\n",
    "        for left_edge_len in range(self.word_len_max, 1, -1):\n",
    "            # 剪枝，上边与左边决定了当前矩形的面积\n",
    "            if len(up_edge_word) * left_edge_len <= self.ans_area:\n",
    "                break\n",
    "            if left_edge_len in self.word_map:\n",
    "                # 左首 等于 上首\n",
    "                left_edge_head = up_edge_word[:1]\n",
    "                if left_edge_head in self.word_map[left_edge_len]:\n",
    "                    for left_edge_end in self.word_map[left_edge_len][left_edge_head]:\n",
    "                        for left_edge_word_pos in self.word_map[left_edge_len][left_edge_head][left_edge_end]:\n",
    "                            self.check_right_edge(up_edge_word, self.words[left_edge_word_pos])\n",
    "\n",
    "    # 根据上边、左边，选取右边并准备进行检查\n",
    "    def check_right_edge(self, up_edge_word, left_edge_word):\n",
    "        # 右长 等于 左长，右首 等于 上尾\n",
    "        right_edge_len = len(left_edge_word)\n",
    "        right_edge_head = up_edge_word[-1:]\n",
    "\n",
    "        if right_edge_head in self.word_map[right_edge_len]:\n",
    "            for right_edge_end in self.word_map[right_edge_len][right_edge_head]:\n",
    "                for right_edge_word_pos in self.word_map[right_edge_len][right_edge_head][right_edge_end]:\n",
    "                    self.check_down_edge(up_edge_word, left_edge_word, self.words[right_edge_word_pos])\n",
    "\n",
    "    # 根据上边、左边、右边，选取下边并准备进行检查\n",
    "    def check_down_edge(self, up_edge_word, left_edge_word, right_edge_word):\n",
    "        # 下长 等于 上长，下首 等于 左尾，下尾 等于 右尾\n",
    "        down_edge_len = len(up_edge_word)\n",
    "        down_edge_head = left_edge_word[-1:]\n",
    "        down_edge_end = right_edge_word[-1:]\n",
    "        if down_edge_head in self.word_map[down_edge_len]:\n",
    "            if down_edge_end in self.word_map[down_edge_len][down_edge_head]:\n",
    "                for down_edge_word_pos in self.word_map[down_edge_len][down_edge_head][down_edge_end]:\n",
    "                    self.check_frame(up_edge_word, left_edge_word, right_edge_word, self.words[down_edge_word_pos])\n",
    "\n",
    "    # 对构造出的框架进行检查，先粗筛，后细查\n",
    "    def check_frame(self, up_edge_word, left_edge_word, right_edge_word, down_edge_word):\n",
    "        # 先做快速检查，同时得到一个包含了全部可能性的数组\n",
    "        demo_box = self.quick_check(up_edge_word, left_edge_word, right_edge_word, down_edge_word)\n",
    "        if not demo_box:\n",
    "            return\n",
    "\n",
    "        # 接下来做完全检查\n",
    "        check_ans = self.full_check(demo_box)\n",
    "        if check_ans:\n",
    "            self.ans_rect = check_ans\n",
    "            self.ans_area = len(check_ans) * len(check_ans[0])\n",
    "\n",
    "    # 快速检查，先粗略的检查框架是否稳固（是否存在符合框架纵横相应长度和首尾的字符串）\n",
    "    def quick_check(self, up_edge_word, left_edge_word, right_edge_word, down_edge_word):\n",
    "        # 先查纵列，因为纵列暂时不存\n",
    "        for col in range(1, len(up_edge_word) - 1):\n",
    "            if not self.find_str_by(len(left_edge_word), up_edge_word[col:col + 1], down_edge_word[col:col + 1]):\n",
    "                return None\n",
    "\n",
    "        # 再查横排，横排顺手存下来（注意每个位置存的都是字符串数组，代表了所有可能）\n",
    "        demo_box = [[up_edge_word]]\n",
    "        for row in range(1, len(left_edge_word) - 1):\n",
    "            find_res = self.find_str_by(len(up_edge_word), left_edge_word[row:row + 1], right_edge_word[row:row + 1])\n",
    "            if not find_res:\n",
    "                return None\n",
    "            else:\n",
    "                demo_box.append(find_res)\n",
    "        # 别忘了加上最后一行\n",
    "        demo_box.append([down_edge_word])\n",
    "        return demo_box\n",
    "\n",
    "    # 根据长度和首尾字符，返回匹配字符串数组\n",
    "    def find_str_by(self, str_len, str_head, str_end):\n",
    "        if str_len in self.word_map:\n",
    "            if str_head in self.word_map[str_len]:\n",
    "                if str_end in self.word_map[str_len][str_head]:\n",
    "                    return list(map(lambda x: self.words[x], self.word_map[str_len][str_head][str_end]))\n",
    "        return None\n",
    "\n",
    "    # 生成并检查全部存在可能的矩形\n",
    "    def full_check(self, demo_box, line=0):\n",
    "        # 矩形生成完毕，就拿去检查一下\n",
    "        if line >= len(demo_box):\n",
    "            word_box = list(map(lambda x: x[0], demo_box))\n",
    "            if self.box_check(word_box):\n",
    "                return word_box\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        # 因为存在多种可能性，此处递归一下，将每一行处理成只有一种情况\n",
    "        for str_canbe in demo_box[line]:\n",
    "            box_copy = copy.deepcopy(demo_box)\n",
    "            box_copy[line] = [str_canbe]\n",
    "            check_res = self.full_check(box_copy, line + 1)\n",
    "            if check_res:\n",
    "                return check_res\n",
    "        return None\n",
    "\n",
    "    # 检查具体的一个个矩形\n",
    "    def box_check(self, word_box):\n",
    "        # 四边在生成的时候已经检查过了\n",
    "        # 横向直接是使用单词生成的\n",
    "        # 所以只需要检查纵向部分就好\n",
    "        for col in range(1, len(word_box[0]) - 2):\n",
    "            check_word = \"\"\n",
    "            for row in range(0, len(word_box)):\n",
    "                check_word += word_box[row][col]\n",
    "            if check_word not in self.word_all:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        dict_tree = {}\n",
    "        def addword(word):\n",
    "            record = dict_tree\n",
    "            for c in word:\n",
    "                if c not in record:\n",
    "                    record[c] = {}\n",
    "                record = record[c]\n",
    "            record['end'] = True\n",
    "        \n",
    "        length_dict = collections.defaultdict(list)\n",
    "        for word in words:\n",
    "            length_dict[len(word)].append(word)\n",
    "            addword(word)\n",
    "        \n",
    "        length_arr = sorted(length_dict.keys(), reverse=True)\n",
    "        area = 0\n",
    "        # print(dict_tree)\n",
    "        # print(length_dict)\n",
    "        # print(length_arr)\n",
    "\n",
    "        def dfs(array, length, cur):\n",
    "            print(cur)\n",
    "            flag = True\n",
    "            for arr in array:\n",
    "                if 'end' not in arr:\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                nonlocal area, res\n",
    "                cur_area = length*len(cur)\n",
    "                # print(cur, cur_area, area)\n",
    "                if cur_area > area:\n",
    "                    area = cur_area\n",
    "                    res = cur\n",
    "            for word in length_dict[length]:\n",
    "                cur_word = True\n",
    "                temp = array[:]\n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in array[i]:\n",
    "                        cur_word = False\n",
    "                        break\n",
    "                    temp[i] = temp[i][c]\n",
    "                if cur_word:\n",
    "                    dfs(temp, length, cur+[word])\n",
    "\n",
    "        res = []\n",
    "        for length in length_arr:\n",
    "            if length*length_arr[0] > area:\n",
    "                dfs([dict_tree]*length, length, [])\n",
    "                # print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasConflict(self, pre, height, predict) -> bool:\n",
    "        if pre not in predict:\n",
    "            return True\n",
    "        for s in predict[pre]:\n",
    "            if len(s) == height:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def rewinder(self, rectangle, width, wlist, height, hlist, predict):\n",
    "        \"\"\" 检测与 hlist 是否冲突，并尝试加入 wlist 单词 \"\"\"\n",
    "        # 检测有无冲突\n",
    "        if len(rectangle) > 0:\n",
    "            for j in range(width):\n",
    "                if self.hasConflict(\n",
    "                    \"\".join([ s[j] for s in rectangle ])\n",
    "                    , height, predict\n",
    "                ): return\n",
    "        # 填充完毕，结算\n",
    "        if len(rectangle) == height:\n",
    "            self.maxsize = width * height\n",
    "            self.ans = rectangle.copy()\n",
    "            return\n",
    "        # 填充未完毕，继续尝试填充\n",
    "        for s in wlist:\n",
    "            rectangle.append(s)\n",
    "            self.rewinder(rectangle, width, wlist, height, hlist, predict)\n",
    "            rectangle.pop()\n",
    "\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        \"\"\" MAIN \"\"\"\n",
    "        \"\"\" 暴力枚举 + 剪枝 + 回溯 \"\"\"\n",
    "        sizes = defaultdict(list)\n",
    "        predict = defaultdict(list)\n",
    "        # 长度-词 & 前缀-词 字典\n",
    "        for s in words:\n",
    "            sizes[len(s)].append(s)\n",
    "            for j in range(1, len(s) + 1):\n",
    "                predict[s[: j]].append(s)\n",
    "        \n",
    "        # 暴力列举所有矩阵大小\n",
    "        self.maxsize = 0\n",
    "        self.ans = []\n",
    "        for width, height in product(sizes, sizes):\n",
    "            if width * height <= self.maxsize:\n",
    "                continue\n",
    "            self.rewinder([], width, sizes[width], height, sizes[height], predict)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasConflict(self, pre, height, predict) -> bool:\n",
    "        if pre not in predict:\n",
    "            return True\n",
    "        for s in predict[pre]:\n",
    "            if len(s) == height:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def rewinder(self, rectangle, width, wlist, height, hlist, predict):\n",
    "        \"\"\" 检测与 hlist 是否冲突，并尝试加入 wlist 单词 \"\"\"\n",
    "        # 检测有无冲突\n",
    "        if len(rectangle) > 0:\n",
    "            for j in range(width):\n",
    "                if self.hasConflict(\n",
    "                    \"\".join([ s[j] for s in rectangle ])\n",
    "                    , height, predict\n",
    "                ): return\n",
    "        # 填充完毕，结算\n",
    "        if len(rectangle) == height:\n",
    "            self.maxsize = width * height\n",
    "            self.ans = rectangle.copy()\n",
    "            return\n",
    "        # 填充未完毕，继续尝试填充\n",
    "        for s in wlist:\n",
    "            rectangle.append(s)\n",
    "            self.rewinder(rectangle, width, wlist, height, hlist, predict)\n",
    "            rectangle.pop()\n",
    "\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        \"\"\" MAIN \"\"\"\n",
    "        \"\"\" 暴力枚举 + 剪枝 + 回溯 \"\"\"\n",
    "        sizes = defaultdict(list)\n",
    "        predict = defaultdict(list)\n",
    "        # 长度-词 & 前缀-词 字典\n",
    "        for s in words:\n",
    "            sizes[len(s)].append(s)\n",
    "            for j in range(1, len(s) + 1):\n",
    "                predict[s[: j]].append(s)\n",
    "        \n",
    "        # 暴力列举所有矩阵大小\n",
    "        self.maxsize = 0\n",
    "        self.ans = []\n",
    "        for width, height in product(sizes, sizes):\n",
    "            if width * height <= self.maxsize:\n",
    "                continue\n",
    "            self.rewinder([], width, sizes[width], height, sizes[height], predict)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def addWord(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur[0]:\n",
    "                cur[0][c] = [{}, False]\n",
    "            cur = cur[0][c]\n",
    "        cur[1] = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "\n",
    "        def dfs(arr, li):\n",
    "            for word in words:\n",
    "                if len(word) != len(arr):   continue\n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in arr[i][0]: break\n",
    "                else:\n",
    "                    temp = arr[:]\n",
    "                    flag = True\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i][0][c]\n",
    "                        flag &= temp[i][1]\n",
    "                    li.append(word)\n",
    "                    if flag:\n",
    "                        h, w = len(li), len(word)\n",
    "                        nonlocal area, res\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = li[:]\n",
    "                    dfs(temp, li)\n",
    "                    li.pop()\n",
    "\n",
    "        ll = sorted(set(len(word) for word in words), reverse = True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:   break\n",
    "            dfs([trie.root] * l, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def addWord(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur[0]:\n",
    "                cur[0][c] = [{}, False]\n",
    "            cur = cur[0][c]\n",
    "        cur[1] = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "\n",
    "        def dfs(arr, li):\n",
    "            for word in words:\n",
    "                if len(word) != len(arr):   continue\n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in arr[i][0]: break\n",
    "                else:\n",
    "                    temp = arr[:]\n",
    "                    flag = True\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i][0][c]\n",
    "                        flag &= temp[i][1]\n",
    "                    li.append(word)\n",
    "                    if flag:\n",
    "                        h, w = len(li), len(word)\n",
    "                        nonlocal area, res\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = li[:]\n",
    "                    dfs(temp, li)\n",
    "                    li.pop()\n",
    "\n",
    "        ll = sorted(set(len(word) for word in words), reverse = True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:   break\n",
    "            dfs([trie.root] * l, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def addWord(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur[0]:\n",
    "                cur[0][c] = [{}, False]\n",
    "            cur = cur[0][c]\n",
    "        cur[1] = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "\n",
    "        def dfs(arr, li):\n",
    "            for word in words:\n",
    "                if len(word) != len(arr):   continue\n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in arr[i][0]: break\n",
    "                else:\n",
    "                    temp = arr[:]\n",
    "                    flag = True\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i][0][c]\n",
    "                        flag &= temp[i][1]\n",
    "                    li.append(word)\n",
    "                    if flag:\n",
    "                        h, w = len(li), len(word)\n",
    "                        nonlocal area, res\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = li[:]\n",
    "                    dfs(temp, li)\n",
    "                    li.pop()\n",
    "\n",
    "        ll = sorted(set(len(word) for word in words), reverse = True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:   break\n",
    "            dfs([trie.root] * l, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "\n",
    "    def addWord(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur[0]:\n",
    "                cur[0][c] = [{}, False]\n",
    "            cur = cur[0][c]\n",
    "        cur[1] = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "\n",
    "        def dfs(arr, li):\n",
    "            for word in words:\n",
    "                #长度不为l不允许匹配\n",
    "                if len(word) != len(arr):   continue\n",
    "                #不好理解可以换成下面的if但会耗时更多\n",
    "                # for i, c in enumerate(word):\n",
    "                #     if c not in arr[i][0]: break\n",
    "                # else:\n",
    "                #要单词的第i个字符，可以作为这一行第i个字符\n",
    "                #arr[i]表示这一行该位置允许放置的字符串\n",
    "                if all(c in arr[i][0] for i,c in enumerate(word)):\n",
    "                    temp = arr[:]\n",
    "                    flag = True\n",
    "                    #为单词中每个字符找到下一行匹配的可能性\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i][0][c]\n",
    "                        flag &= temp[i][1]\n",
    "                    #li中增加该字符串的可能性\n",
    "                    li.append(word)\n",
    "                    #如果这一行每个字符都是一个单词的结尾（flag == True），那么更新答案\n",
    "                    if flag:\n",
    "                        h, w = len(li), len(word)\n",
    "                        nonlocal area, res\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = li[:]\n",
    "                    dfs(temp, li)\n",
    "                    #已经试过该字符串的可能性删除\n",
    "                    li.pop()\n",
    "\n",
    "        ll = sorted(set(len(word) for word in words), reverse = True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:   break\n",
    "            dfs([trie.root] * l, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "\n",
    "    def addWord(self, word: str):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur[0]:\n",
    "                cur[0][c] = [{}, False]\n",
    "            cur = cur[0][c]\n",
    "        cur[1] = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        \n",
    "        # 将所有单词添加到Trie中\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "\n",
    "        # 深度优先搜索\n",
    "        def dfs(arr, li):\n",
    "            nonlocal area, res\n",
    "            for word in words:\n",
    "                if len(word) != len(arr):\n",
    "                    continue\n",
    "                \n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in arr[i][0]:\n",
    "                        break\n",
    "                else:\n",
    "                    temp = arr[:]\n",
    "                    flag = True\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i][0][c]\n",
    "                        flag &= temp[i][1]\n",
    "                    \n",
    "                    li.append(word)\n",
    "                    \n",
    "                    if flag:\n",
    "                        h, w = len(li), len(word)\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = li[:]\n",
    "                    \n",
    "                    dfs(temp, li)\n",
    "                    li.pop()\n",
    "\n",
    "        # 对所有单词的长度进行排序，并按照降序进行处理\n",
    "        ll = sorted(set(len(word) for word in words), reverse=True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:\n",
    "                break\n",
    "            dfs([trie.root] * l, [])\n",
    "        \n",
    "        return res\n",
    "\n",
    "# 测试代码\n",
    "if __name__ == \"__main__\":\n",
    "    sol = Solution()\n",
    "    words = [\"this\", \"real\", \"is\", \"a\", \"test\"]\n",
    "    print(sol.maxRectangle(words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def addWord(self, word):\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            if c not in cur[0]:\n",
    "                cur[0][c] = [{}, False]\n",
    "            cur = cur[0][c]\n",
    "        cur[1] = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.addWord(word)\n",
    "\n",
    "        def dfs(arr, li):\n",
    "            for word in words:\n",
    "                if len(word) != len(arr):   continue\n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in arr[i][0]: break\n",
    "                else:\n",
    "                    temp = arr[:]\n",
    "                    flag = True\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i][0][c]\n",
    "                        flag &= temp[i][1]\n",
    "                    li.append(word)\n",
    "                    if flag:\n",
    "                        h, w = len(li), len(word)\n",
    "                        nonlocal area, res\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = li[:]\n",
    "                    dfs(temp, li)\n",
    "                    li.pop()\n",
    "\n",
    "        ll = sorted(set(len(word) for word in words), reverse = True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:   break\n",
    "            dfs([trie.root] * l, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasConflict(self, pre, height, predict) -> bool:\n",
    "        return (pre, height) not in predict\n",
    "\n",
    "    def rewinder(self, rectangle, width, wlist, height, hlist, predict):\n",
    "        \"\"\" 检测与 hlist 是否冲突，并尝试加入 wlist 单词 \"\"\"\n",
    "        # 检测有无冲突\n",
    "        if len(rectangle) > 0:\n",
    "            for j in range(width):\n",
    "                if self.hasConflict(\n",
    "                    \"\".join([ s[j] for s in rectangle ])\n",
    "                    , height, predict\n",
    "                ): return\n",
    "        # 填充完毕，结算\n",
    "        if len(rectangle) == height:\n",
    "            self.maxsize = width * height\n",
    "            self.ans = rectangle.copy()\n",
    "            return\n",
    "        # 填充未完毕，继续尝试填充\n",
    "        for s in wlist:\n",
    "            rectangle.append(s)\n",
    "            self.rewinder(rectangle, width, wlist, height, hlist, predict)\n",
    "            rectangle.pop()\n",
    "\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        \"\"\" MAIN \"\"\"\n",
    "        \"\"\" 暴力枚举 + 剪枝 + 回溯 \"\"\"\n",
    "        sizes = defaultdict(list)\n",
    "        predict = defaultdict(list)\n",
    "        # 长度-词 & 前缀-词 字典\n",
    "        for s in words:\n",
    "            sizes[len(s)].append(s)\n",
    "            for j in range(1, len(s) + 1):\n",
    "                predict[(s[: j], len(s))].append(s)\n",
    "        \n",
    "        # 暴力列举所有矩阵大小\n",
    "        self.maxsize = 0\n",
    "        self.ans = []\n",
    "        for width, height in product(sizes, sizes):\n",
    "            if width * height <= self.maxsize:\n",
    "                continue\n",
    "            self.rewinder([], width, sizes[width], height, sizes[height], predict)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_word = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            if ch not in node.children:\n",
    "                node.children[ch] = TrieNode()\n",
    "            node = node.children[ch]\n",
    "        node.is_word = True\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        area = 0\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "\n",
    "        def dfs(arr: List[TrieNode], path: List[str]):\n",
    "            for word in words:\n",
    "                if len(word) != len(arr):\n",
    "                    continue\n",
    "                for i, c in enumerate(word):\n",
    "                    if c not in arr[i].children:\n",
    "                        break\n",
    "                else:\n",
    "                    flag = True\n",
    "                    temp = arr.copy()\n",
    "                    # 若全部为单词结尾\n",
    "                    for i, c in enumerate(word):\n",
    "                        temp[i] = temp[i].children[c]\n",
    "                        flag &= temp[i].is_word\n",
    "                    path.append(word)\n",
    "                    if flag:\n",
    "                        h, w = len(path), len(word)\n",
    "                        nonlocal area, res\n",
    "                        if h * w > area:\n",
    "                            area = h * w\n",
    "                            res = path.copy()\n",
    "                    dfs(temp, path)\n",
    "                    path.pop()\n",
    "        # 枚举单词长度\n",
    "        ll = sorted(set(len(word) for word in words), reverse = True)\n",
    "        for l in ll:\n",
    "            if l * ll[0] < area:\n",
    "                break\n",
    "            dfs([trie.root] * l, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 0. 定义字典树\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.is_leaf = False\n",
    "        self.children = {}\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        max_area = 0\n",
    "        res = None\n",
    "        # 1. 对不同长度的单词分组, 将所有单词加入字典树\n",
    "        word_dict = defaultdict(set)\n",
    "        for word in words:\n",
    "            word_dict[len(word)].add(word)\n",
    "            cur_node = root\n",
    "            for c in word:\n",
    "                if c not in cur_node.children:\n",
    "                    cur_node.children[c] = Trie()\n",
    "                cur_node = cur_node.children[c]\n",
    "            cur_node.is_leaf = True\n",
    "\n",
    "        # 2. 回溯所有可能性, 每次从set中选出一个单词作为一行\n",
    "        def dfs(cur_words, selected_set):\n",
    "            nonlocal max_area, res\n",
    "            if len(selected_set) == 0 or len(selected_set) * len(list(selected_set)[0]) < max_area: return\n",
    "            for word in selected_set:\n",
    "                cur_words.append(word)\n",
    "                judge = is_valid(cur_words, root)\n",
    "                if judge == 0:\n",
    "                    cur_words.pop()\n",
    "                elif judge == 1 or judge == 2:\n",
    "                    if judge == 2 and len(cur_words) * len(cur_words[0]) > max_area :\n",
    "                        max_area = len(cur_words) * len(cur_words[0])\n",
    "                        res = [w for w in cur_words]\n",
    "                    dfs(cur_words, words)\n",
    "                    cur_words.pop()\n",
    "\n",
    "        # 3. 判断当前的选择是否合法, 0表示字典树未命中, 1表示字典树命中, 2表示字典树命中且根节点\n",
    "        def is_valid(cur_words, root):\n",
    "            m, n = len(cur_words), len(cur_words[0])\n",
    "            is_leaf = True\n",
    "            for j in range(n):\n",
    "                cur_node = root\n",
    "                for i in range(m):\n",
    "                    cur_char = cur_words[i][j]\n",
    "                    if cur_char not in cur_node.children: return 0\n",
    "                    cur_node = cur_node.children[cur_char]\n",
    "                if not cur_node.is_leaf: is_leaf = False\n",
    "            return 2 if is_leaf else 1\n",
    "        \n",
    "        for words in word_dict.values():\n",
    "            dfs([], words)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 0. 定义字典树\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.is_leaf = False\n",
    "        self.children = {}\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        max_area = 0\n",
    "        res = None\n",
    "        # 1. 对不同长度的单词分组, 将所有单词加入字典树\n",
    "        word_dict = defaultdict(set)\n",
    "        for word in words:\n",
    "            word_dict[len(word)].add(word)\n",
    "            cur_node = root\n",
    "            for c in word:\n",
    "                if c not in cur_node.children:\n",
    "                    cur_node.children[c] = Trie()\n",
    "                cur_node = cur_node.children[c]\n",
    "            cur_node.is_leaf = True\n",
    "\n",
    "        # 2. 回溯所有可能性, 每次从set中选出一个单词作为一行\n",
    "        def dfs(cur_words, selected_set):\n",
    "            nonlocal max_area, res\n",
    "            if len(selected_set) == 0: return\n",
    "            for word in selected_set:\n",
    "                cur_words.append(word)\n",
    "                judge = is_valid(cur_words, root)\n",
    "                if judge == 0:\n",
    "                    cur_words.pop()\n",
    "                elif judge == 1 or judge == 2:\n",
    "                    if judge == 2 and len(cur_words) * len(cur_words[0]) > max_area :\n",
    "                        max_area = len(cur_words) * len(cur_words[0])\n",
    "                        res = [w for w in cur_words]\n",
    "                    dfs(cur_words, words)\n",
    "                    cur_words.pop()\n",
    "\n",
    "        # 3. 判断当前的选择是否合法, 0表示字典树未命中, 1表示字典树命中, 2表示字典树命中且根节点\n",
    "        def is_valid(cur_words, root):\n",
    "            m, n = len(cur_words), len(cur_words[0])\n",
    "            is_leaf = True\n",
    "            for j in range(n):\n",
    "                cur_node = root\n",
    "                for i in range(m):\n",
    "                    cur_char = cur_words[i][j]\n",
    "                    if cur_char not in cur_node.children: return 0\n",
    "                    cur_node = cur_node.children[cur_char]\n",
    "                if not cur_node.is_leaf: is_leaf = False\n",
    "            return 2 if is_leaf else 1\n",
    "        \n",
    "        # 4. 遍历所有长度的组合, 若改长度的组合已经不可能超过当前面积时, 剪枝\n",
    "        for l in word_dict.keys():\n",
    "            words = word_dict[l]\n",
    "            if l * len(words) > max_area:\n",
    "                dfs([], words)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 0. 定义字典树\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.is_leaf = False\n",
    "        self.children = {}\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        max_area = 0\n",
    "        res = None\n",
    "        # 1. 对不同长度的单词分组, 将所有单词加入字典树\n",
    "        word_dict = defaultdict(set)\n",
    "        for word in words:\n",
    "            word_dict[len(word)].add(word)\n",
    "            cur_node = root\n",
    "            for c in word:\n",
    "                if c not in cur_node.children:\n",
    "                    cur_node.children[c] = Trie()\n",
    "                cur_node = cur_node.children[c]\n",
    "            cur_node.is_leaf = True\n",
    "\n",
    "        # 2. 回溯所有可能性, 每次从set中选出一个单词作为一行\n",
    "        def dfs(cur_words, selected_set):\n",
    "            nonlocal max_area, res\n",
    "            if len(selected_set) == 0: return\n",
    "            for word in selected_set:\n",
    "                cur_words.append(word)\n",
    "                judge = is_valid(cur_words, root)\n",
    "                if judge == 0:\n",
    "                    cur_words.pop()\n",
    "                elif judge == 1 or judge == 2:\n",
    "                    if judge == 2 and len(cur_words) * len(cur_words[0]) > max_area :\n",
    "                        max_area = len(cur_words) * len(cur_words[0])\n",
    "                        res = [w for w in cur_words]\n",
    "                    dfs(cur_words, words)\n",
    "                    cur_words.pop()\n",
    "\n",
    "        # 3. 判断当前的选择是否合法, 0表示字典树未命中, 1表示字典树命中, 2表示字典树命中且根节点\n",
    "        def is_valid(cur_words, root):\n",
    "            m, n = len(cur_words), len(cur_words[0])\n",
    "            is_leaf = True\n",
    "            for j in range(n):\n",
    "                cur_node = root\n",
    "                for i in range(m):\n",
    "                    cur_char = cur_words[i][j]\n",
    "                    if cur_char not in cur_node.children: return 0\n",
    "                    cur_node = cur_node.children[cur_char]\n",
    "                if not cur_node.is_leaf: is_leaf = False\n",
    "            return 2 if is_leaf else 1\n",
    "        \n",
    "        for words in word_dict.values():\n",
    "            if len(words) * len(list(words)[0]) > max_area:\n",
    "                dfs([], words)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, parent: Optional[\"Trie\"] = None) -> None:\n",
    "        self.parent = parent\n",
    "        self.kids = {}\n",
    "        self.is_word = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        len_words = {}\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if len(word) not in len_words:\n",
    "                len_words[len(word)] = [word]\n",
    "            else:\n",
    "                len_words[len(word)].append(word)\n",
    "            temp = root\n",
    "            for c in word:\n",
    "                if c not in temp.kids:\n",
    "                    temp.kids[c] = Trie(temp)\n",
    "                temp = temp.kids[c]\n",
    "            temp.is_word = True\n",
    "        word_lens = list(len_words.keys())\n",
    "        word_lens.sort(reverse=True)\n",
    "        max_area = 0\n",
    "        max_rectangle = []\n",
    "        for row_len in word_lens:\n",
    "            if row_len * word_lens[0] < max_area:\n",
    "                break\n",
    "            temp_rectangle = self.search(\n",
    "                [root for _ in range(row_len)], len_words[row_len], []\n",
    "            )\n",
    "            area = row_len * len(temp_rectangle)\n",
    "            if area > max_area:\n",
    "                max_area = area\n",
    "                max_rectangle = [w for w in temp_rectangle]\n",
    "        return max_rectangle\n",
    "\n",
    "    def search(\n",
    "        self, col_tries: List[Trie], len_words: List[str], temp_rectangle: List[str]\n",
    "    ) -> List[str]:\n",
    "        max_area = 0\n",
    "        max_rectangle = []\n",
    "        for word in len_words:\n",
    "            valid1 = True\n",
    "            for i in range(len(word)):\n",
    "                if word[i] not in col_tries[i].kids:\n",
    "                    valid1 = False\n",
    "                    break\n",
    "            if valid1:\n",
    "                for i in range(len(word)):\n",
    "                    col_tries[i] = col_tries[i].kids[word[i]]\n",
    "                valid2 = True\n",
    "                for i in range(len(word)):\n",
    "                    if not col_tries[i].is_word:\n",
    "                        valid2 = False\n",
    "                        break\n",
    "                if valid2:\n",
    "                    area = (len(temp_rectangle) + 1) * len(word)\n",
    "                    if area > max_area:\n",
    "                        max_area = area\n",
    "                        max_rectangle = temp_rectangle + [word]\n",
    "                new_max_rectangle = self.search(\n",
    "                    col_tries, len_words, temp_rectangle + [word]\n",
    "                )\n",
    "                new_area = len(word) * len(new_max_rectangle)\n",
    "                if new_area > max_area:\n",
    "                    max_area = new_area\n",
    "                    max_rectangle = new_max_rectangle\n",
    "                for i in range(len(word)):\n",
    "                    col_tries[i] = col_tries[i].parent\n",
    "        return max_rectangle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 0. 定义字典树\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.is_leaf = False\n",
    "        self.children = {}\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        max_area = 0\n",
    "        res = None\n",
    "        # 1. 对不同长度的单词分组, 将所有单词加入字典树\n",
    "        word_dict = defaultdict(set)\n",
    "        for word in words:\n",
    "            word_dict[len(word)].add(word)\n",
    "            cur_node = root\n",
    "            for c in word:\n",
    "                if c not in cur_node.children:\n",
    "                    cur_node.children[c] = Trie()\n",
    "                cur_node = cur_node.children[c]\n",
    "            cur_node.is_leaf = True\n",
    "\n",
    "        # 2. 回溯所有可能性, 每次从set中选出一个单词作为一行\n",
    "        def dfs(cur_words, selected_set):\n",
    "            nonlocal max_area, res\n",
    "            if len(selected_set) == 0: return\n",
    "            for word in selected_set:\n",
    "                cur_words.append(word)\n",
    "                judge = is_valid(cur_words, root)\n",
    "                if judge == 0:\n",
    "                    cur_words.pop()\n",
    "                elif judge == 1 or judge == 2:\n",
    "                    if judge == 2 and len(cur_words) * len(cur_words[0]) > max_area :\n",
    "                        max_area = len(cur_words) * len(cur_words[0])\n",
    "                        res = [w for w in cur_words]\n",
    "                    dfs(cur_words, words)\n",
    "                    cur_words.pop()\n",
    "\n",
    "        # 3. 判断当前的选择是否合法, 0表示字典树未命中, 1表示字典树命中, 2表示字典树命中且根节点\n",
    "        def is_valid(cur_words, root):\n",
    "            m, n = len(cur_words), len(cur_words[0])\n",
    "            is_leaf = True\n",
    "            for j in range(n):\n",
    "                cur_node = root\n",
    "                for i in range(m):\n",
    "                    cur_char = cur_words[i][j]\n",
    "                    if cur_char not in cur_node.children: return 0\n",
    "                    cur_node = cur_node.children[cur_char]\n",
    "                if not cur_node.is_leaf: is_leaf = False\n",
    "            return 2 if is_leaf else 1\n",
    "        \n",
    "        for l in sorted(word_dict.keys(), reverse=True):\n",
    "            words = word_dict[l]\n",
    "            if l * len(words) > max_area:\n",
    "                dfs([], words)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRectangle(self, words: List[str]) -> List[str]:\n",
    "        # 根据长度、首字符\n",
    "        d = defaultdict(lambda: defaultdict(list))\n",
    "\n",
    "        # 所有从首字符开始，长度大于等于2的可能性\n",
    "        ws = set(words)\n",
    "\n",
    "        for w in words:\n",
    "            n = len(w)\n",
    "            d[n][w[0]].append(w)\n",
    "            d[n][0].append(w)\n",
    "\n",
    "            for i in range(2, n):\n",
    "                ws.add(w[:i])\n",
    "\n",
    "        # 字符串长度，从大到小\n",
    "        ln = list(d)\n",
    "        ln.sort(reverse=True)\n",
    "\n",
    "        # 循环每个字母作为首字母\n",
    "        maxmj = 0\n",
    "        ret = []\n",
    "\n",
    "        for m in ln:\n",
    "            for w in d[m][0]:\n",
    "                for n, dn in d.items():\n",
    "                    if n > m or maxmj >= m * n:\n",
    "                        continue\n",
    "\n",
    "                    l = [dn[c] for c in w]\n",
    "\n",
    "                    # 考虑对象性，要求n < m，或者n = m时w >= l[0]中元素\n",
    "                    if n == m:\n",
    "                        l0 = l[0][:]\n",
    "                        for i in range(len(l0) - 1, -1, -1):\n",
    "                            if l0[i] > w:\n",
    "                                del l0[i]\n",
    "                                break\n",
    "\n",
    "                        if not l0:\n",
    "                            continue\n",
    "                        l[0] = l0\n",
    "\n",
    "                    # 从l中获取\n",
    "                    def get(now, i=0):\n",
    "                        if i > 1:\n",
    "                            if not all(e in ws for e in now):\n",
    "                                return\n",
    "                        \n",
    "                        if i == m:\n",
    "                            yield now\n",
    "                            return\n",
    "\n",
    "                        for e in l[i]:\n",
    "                            _now = now[:]\n",
    "                            for j in range(n - 1):\n",
    "                                _now[j] += e[j + 1]\n",
    "                            yield from get(_now, i + 1)\n",
    "\n",
    "                    for one in get([\"\"] * (n - 1)):\n",
    "                        maxmj = m * n\n",
    "                        ret = [w] + one\n",
    "                        break\n",
    "\n",
    "        return ret\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
